package com.linwen.excise.od;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。
 * <p>
 * 现有两组字母，分别表示后序遍历（左孩子->右孩子->父节点）和中序遍历（左孩子->父节点->右孩子）的结果，请你输出层序遍历的结果。
 * <p>
 * 输入
 * <p>
 * 每个输入文件一行，第一个字符串表示后序遍历结果，第二个字符串表示中序遍历结果。（每串只包含大写字母）
 * <p>
 * 中间用单空格分隔。
 * <p>
 * 输出
 * <p>
 * 输出仅一行，表示层序遍历的结果，结尾换行。
 * <p>
 * 示例1   输入输出示例仅供调试，后台判题数据一般不包含示例
 * <p>
 * 输入
 * <p>
 * CBEFDA CBAEDF
 * <p>
 * 输出
 * <p>
 * ABDCEF
 */
public class _二叉树层次遍历 {
    // 二叉树节点及二叉树的定义，常用可记下来
    private static class Node {
        char data;
        Node left;
        Node right;

        public Node(char data) {
            this.data = data;
        }
    }

    private static class Tree {
        Node root;

        public Tree() {
            this.root = null;
        }

        public static Tree createTree(char[] post_order, char[] in) {
            Tree res = new Tree();
            res.root = createTree(post_order, 0, post_order.length - 1, in, 0, in.length - 1);
            return res;
        }

        private static Node createTree(char[] post_order, int s1, int end1, char[] in, int s2, int end2) {
            if (s1 > end1 || s2 > end2) {
                return null;
            }
            Node root = new Node(post_order[end1]);
            for (int i = s2; i <= end2; i++) {
                if (post_order[end1] == in[i]) {
                    root.left = createTree(post_order, s1, s1 + i - s2 - 1, in, s2, i - 1);
                    root.right = createTree(post_order, s1 + i - s2, end1 - 1, in, i + 1, end2);
                    break;
                }
            }
            return root;
        }
    }

    public static void main(String[] args) {
        // 处理输入
        Scanner in = new Scanner(System.in);
        String[] params = in.nextLine().split(" ");
        char[] post_order = params[0].toCharArray();
        char[] mid_order = params[1].toCharArray();
        Tree t = Tree.createTree(post_order, mid_order);
        ArrayList<Character> layer_res = new ArrayList<>();
        if (t.root != null) {
            Queue<Node> queue = new LinkedList<>();
            queue.offer(t.root);
            while (!queue.isEmpty()) {
                Node node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                layer_res.add(node.data);
            }
        }


        StringBuilder result = new StringBuilder();
        layer_res.forEach(result::append);
        System.out.println(result);
    }

}
